HSAGA and its application for the construction of near-Moore digraphs

Title: HSAGA and its application for the construction of near-Moore digraphs
Creator: Tang, Jianmin; Miller, Mirka; Lin, Yuqing
Relation: Journal of Discrete Algorithms Vol. 6, Issue 1, p. 73-84
Publisher Link: http://dx.doi.org/10.1016/j.jda.2007.05.003
Publisher: Elsevier
Resource Type: journal article
Date: 2008
Description: The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions. This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems.
Subject: Moore bound; diameter; out-degree; simulated annealing; genetic algorithm; degree/diameter problem
Identifier: http://hdl.handle.net/1959.13/42820
Identifier: uon:4975
Identifier: ISSN:1570-8667
Language: eng
Full Text
Reviewed

		Thumbnail	File	Description	Size	Format
View Details Download			SOURCE1	Author final version	651 KB	Adobe Acrobat PDF	View Details Download